import java.util.*;

/**
 * @author LKQ
 * @date 2022/3/7 16:25
 * @description 行二分，找到行中最大元素所在的列，
 */
public class Solution {
    public static void main(String[] args) {

    }
    public int[] findPeakGrid(int[][] mat) {
        int m = mat.length;
        int low = 0, high = m - 1;
        int preMax , curMax , nextMax;
        int col1, col2, col3;
        while (low <= high) {
            // 中间行
            int mid = (low + high) / 2;
            col2 = findMaxIndex(mat, mid);
            if (low == high) {
                return new int[]{mid, col2};
            }
            col1 = findMaxIndex(mat, mid - 1);
            col3 = findMaxIndex(mat, mid + 1);
            preMax = mid - 1 >= 0 ? mat[mid-1][col1] : -1;
            nextMax = mid + 1 < m ? mat[mid + 1][col3] : -1;
            curMax = mat[mid][col2];
            if (curMax >= preMax && curMax >= nextMax) {
                return new int[]{mid, col2};
            }
            // mid - 1行最大
            if (preMax > nextMax && preMax >= curMax) {
                high = mid - 1;
            }else  {
                low = mid;
            }
        }
        return null;
    }
    public int findMaxIndex(int[][] mat, int row) {
        if (row < 0 || row >= mat.length) {
            return -1;
        }
        // 最大值所在的列下标
        int j = 0;
        for (int i = 0; i < mat[0].length; i++) {
            if (mat[row][i] > mat[row][j]) {
                j = i;
            }
        }
        return j;
    }
}
